Troxacitabine is a cytotoxic L-enantiomer nucleoside analog which appears to inhibit DNA polymerases and act as a complete DNA chain terminator. Since it can inhibit DNA replication and repair, it is an attractive candidate for combination with agents such as cisplatin that cause DNA damage. This Phase I study of Troxacitabine in combination with cisplatin will determine the maximum tolerated dose of the combination.